
\section{Parallel Quadratic Programming Algorithm}

\label{sec:pqp-alg}

A typical quadratic program can be represented as

\begin{subequations}
\label{eq:primalProblem}
\begin{align}
\min_{U} & \frac{1}{2}U^TPU + H^TU  \label{eq:primalCost}\\
& s.t. VU \leq W
\end{align}
\end{subequations}

If the matrix $P$ is positive definite and the primal problem is feasible (which
is true for the HVAC system application and many other MPC problems), then
according to the PQP algorithm, the corresponding dual problem

\begin{subequations}
\label{eq:DualProblem}
\begin{align}
\min_{\lambda} & \frac{1}{2}\lambda^TQ \lambda + \lambda^T h  \label{eq:dualcost}\\
& s.t. \lambda \geq 0  
\end{align}
\end{subequations}

can be solved using the following iterative scaling of the dual variable
$\lambda$:

\begin{align}
\label{eq:updateRule}
\lambda_i \leftarrow  
\begin{cases}
\lambda_i \left[ \frac{h_i^- + (Q^- \lambda)_i}{h_i^+ + (Q^+ \lambda)_i}
\right] & \text{if}\ (h_i^+ + (Q^+ \lambda)_i) \neq 0\\
0 & \text{otherwise}
\end{cases}
\end{align}

where $\lambda_i$ is the $i^{th}$ element of $\lambda$. $h_{i}^+ = max(h_i,0)$,
$h_{i}^- = max(-h_i,0)$. $Q^+ = max(Q,0) + diag(r)$, $Q^- = max(-Q,0) +
diag(r)$, where $r \geq 0$ is a tuning parameter.  The cost function of the dual
problem is calculated iteratively until it converges to a final value within
some tolerance. Once a solution $\lambda^*$ to the dual problem is found, the
solution $U^*$ to the primal problem can be found easily. A detailed proof of
convergence of the algorithm can be found in ~\cite{PQPMPC}.

For our particular application, $H^T = 0$ in the primal problem, $r = 0$ and the
tolerance we use for the convergence is $1.0 \times 10^{-6}$.

